package com.leetcode.algorithm.y22.m06;

/**
 * 300. 最长递增子序列
 * 
 * https://leetcode.cn/problems/longest-increasing-subsequence/
 * 
 * @author jie.deng
 *
 */
class Question0300Solution01 {

	public int lengthOfLIS(int[] nums) {
		int length = nums.length;
		// DP状态定义:
		// dp[i]表示 某个递增子序列的最后一个元素是nums[i]，这个序列的最长长度为dp[i]
		int[] dp = new int[length];
		dp[0] = 1;

		for (int i = 1; i < dp.length; i++) {
			dp[i] = 1;
			for (int j = i - 1; j >= 0; j--) {
				if (nums[i] > nums[j]) {
					dp[i] = Math.max(dp[i], 1 + dp[j]);
					// WARNING：下面是错误写法
					// dp[i] = 1 + dp[j];break;
				}
			}
		}

		int maxLen = dp[0];
		for (int i = 1; i < dp.length; i++) {
			maxLen = Math.max(maxLen, dp[i]);
		}
		return maxLen;
	}

}